Factoring large integer numbers is a difficult mathematical problem. The problem of integer factorization can be formulated as: given a positive integer, find all the prime factors of the integer. Every positive integer has a unique prime factorization. For small numbers, such as 16, factoring is quite simple. However, as the number increases, in general, finding the factors becomes increasingly difficult. In fact, the problem becomes intractable on known computing devices for large numbers. Conversely, however, confirming that a set of primes is the prime factorization of a number is easy.
One particular set of integers that is interesting to factor are biprimes. Biprimes are integers that are the direct product of two, not necessarily distinct, prime factors. For example, 15 is a biprime since 3 and 5 are the only prime factors and it can be derived by multiplying them together. The factoring of biprimes is of interest in the fields of cryptography and cryptanalysis, among other fields. Some cryptography schemes use the difficulty of factoring large biprimes as the basis for their encryption system. For example, a large biprime is used to encrypt data such that decryption of the data is only possible through the identification of the prime factors of the biprime. Such an encryption scheme is not absolutely secure because it is possible to identify prime factors, albeit through considerable effort. Thus, security of data encrypted in such a manner is only ensured for the period of time that it would take a third party to identify the prime factors for the biprime used to encrypt the data. Thus, such encryption schemes are useful when the amount of time it would take an unauthorized third party to find the prime factors of the encryption is much longer than the amount of time the information would be useful.
Complexity Classes
Complexity theory is the quantitative study of the time it takes for a computer to solve a decision problem and the resources required to solve the decision problem. In logic, a decision problem is determining whether or not there exists a decision procedure or algorithm for a class S of questions requiring a Boolean value (i.e., a true or false, or yes or no). These are also known as yes-or-no questions. Such problems are assigned to complexity classes, the number and type of which is ever changing, as new complexity classes are defined and existing ones merge through the contributions of computer scientists. One exemplary complexity class involves those decision problems that are solvable in polynomial time by a Turing machine (P, herein poly). Another exemplary complexity class involves those decision problems that are solvable in non-deterministic polynomial-time, or problems whose solution is verifiable in polynomial time (NP). Still another complexity class is NP-hard (non-deterministic polynomial-time hard; NPH), which includes decision problems that have been shown to be hard to solve. More specifically, NP-hard refers to the class of decision problems that contains all problems H such that for every decision problem L in NP there exists a polynomial-time many-one reduction to H, written L≦H. Informally, this class can be described as containing the decision problems that are at least as hard as any problem in NP. A decision problem is NP-Complete (NPC) if it is in NP and it is NP-hard.
A problem is equivalent, or harder to solve, than a known problem in NPC if there exists a polynomial time reduction to the instant problem from the known problem in NPC. Reduction can be regarded as a generalization of mapping. The mappings can be a one-to-one function, a many-to-one function, making use of an oracle, etc. The concept of complexity classes and how they define the intractability of certain decision problems is found in, for example, M. R. Garey, D. S. Johnson, 1979, Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman, San Francisco, ISBN: 0716710455, pp. 1-15.
It is not exactly known which complexity classes the integer factorization problem falls under. It is widely believed to be outside P, since there have been many attempts to find a polynomial-time solution but none have worked. It is also suspected to be outside NPC. The integer factorization problem, expressed as a decision problem, where it suffices to answer whether an integer N has a factor less than M, is a known NP problem. Also, the determination of whether an integer is prime, expressed as a decision problem, is a known P problem. In the field of quantum computing, Shor's algorithm for factoring numbers (discussed below) proved that factoring biprimes is in the bounded-error, quantum, polynomial (BQP) complexity class. This means it can be solved by a quantum computer in polynomial time with an error probability of at most 0.25 for all instances.
Quantum Computers
A Turing machine is a theoretical computing system, described in 1936 by Alan Turing. A Turing machine that can efficiently simulate any other Turing machine is called a Universal Turing Machine (UTM). The Church-Turing thesis states that any practical computing model has either the equivalent or a subset of the capabilities of a UTM.
An analog processor is a processor that employs the fundamental properties of a physical system to find the solution to a computation problem. In contrast to a digital processor, which requires an algorithm for finding the solution followed by the execution of each step in the algorithm according to Boolean methods, analog processors do not involve Boolean methods.
A quantum computer is any physical system that harnesses one or more quantum effects to perform a computation. A quantum computer that can efficiently simulate any other quantum computer is called a Universal Quantum Computer (UQC).
In 1981 Richard P. Feynman proposed that quantum computers could be used to solve certain computational problems more efficiently than a UTM and therefore invalidate the Church-Turing thesis. See e.g., Feynman R. P., “Simulating Physics with Computers” International Journal of Theoretical Physics, Vol. 21 (1982) pp. 467-488. For example, Feynman noted that a quantum computer could be used to simulate certain other quantum systems, allowing exponentially faster calculation of certain properties of the simulated quantum system than is possible using a UTM.
There are several general approaches to the design and operation of quantum computers. One such approach is the “circuit model” of quantum computation. In this approach, qubits are acted upon by sequences of logical gates that are the compiled representation of an algorithm. Circuit model quantum computers have several serious barriers to practical implementation. In the circuit model, it is required that qubits remain coherent over time periods much longer than the single-gate time. This requirement arises because circuit model quantum computers require operations that are collectively called quantum error correction in order to operate. Quantum error correction cannot be performed without the circuit model quantum computer's qubits being capable of maintaining quantum coherence over time periods on the order of 1,000 times the single-gate time. Much research has been focused on developing qubits with coherence sufficient to form the basic information units of circuit model quantum computers. See e.g., Shor, P. W. “Introduction to Quantum Algorithms” arXiv.org:quant-ph/0005003 (2001), pp. 1-27. The art is still hampered by an inability to increase the coherence of qubits to acceptable levels for designing and operating practical circuit model quantum computers.
Another approach to quantum computation, called thermally-assisted adiabatic quantum computation, involves using the natural physical evolution of a system of coupled quantum systems as a computational system. This approach does not make critical use of quantum gates and circuits. Instead, starting from a known initial Hamiltonian, it relies upon the guided physical evolution of a system of coupled quantum systems wherein the problem to be solved has been encoded in the system's Hamiltonian, so that the final state of the system of coupled quantum systems contains information relating to the answer to the problem to be solved. This approach does not require long qubit coherence times. Examples of this type of approach include adiabatic quantum computation, cluster-state quantum computation, one-way quantum computation, and quantum annealing, and are described, for example, in Farhi, E. et al., “Quantum Adiabatic Evolution Algorithms versus Simulated Annealing” arXiv.org:quant-ph/0201031 (2002), pp 1-16.
As mentioned previously, qubits can be used as fundamental units of information for a quantum computer. As with bits in UTMs, qubits can refer to at least two distinct quantities; a qubit can refer to the actual physical device in which information is stored, and it can also refer to the unit of information itself, abstracted away from its physical device.
Qubits generalize the concept of a classical digital bit. A classical information storage device can encode two discrete states, typically labeled “0” and “1”. Physically these two discrete states are represented by two different and distinguishable physical states of the classical information storage device, such as direction or magnitude of magnetic field, current or voltage, where the quantity encoding the bit state behaves according to the laws of classical physics. A qubit also contains two discrete physical states, which can also be labeled “0” and “1”. Physically these two discrete states are represented by two different and distinguishable physical states of the quantum information storage device, such as direction or magnitude of magnetic field, current or voltage, where the quantity encoding the bit state behaves according to the laws of quantum physics. If the physical quantity that stores these states behaves quantum mechanically, the device can additionally be placed in a superposition of 0 and 1. That is, the qubit can exist in both a “0” and “1” state at the same time, and so can perform a computation on both states simultaneously. In general, N qubits can be in a superposition of 2N states. Quantum algorithms make use of the superposition property to speed up some computations.
In standard notation, the basis states of a qubit are referred to as the |0 and |1 states. During quantum computation, the state of a qubit, in general, is a superposition of basis states so that the qubit has a nonzero probability of occupying the |0 basis state and a simultaneous nonzero probability of occupying the |1 basis state. Mathematically, a superposition of basis states means that the overall state of the qubit, which is denoted |Ψ, has the form |Ψ=a|0+b|1, where a and b are coefficients corresponding to the probabilities |a|2 and |b|2, respectively. The coefficients a and b each have real and imaginary components. The quantum nature of a qubit is largely derived from its ability to exist in a coherent superposition of basis states. A qubit will retain this ability to exist as a coherent superposition of basis states when the qubit is sufficiently isolated from sources of decoherence.
To complete a computation using a qubit, the state of the qubit is measured (i.e., read out). Typically, when a measurement of the qubit is performed, the quantum nature of the qubit is temporarily lost and the superposition of basis states collapses to either the |0 basis state or the |1 basis state and thus regains its similarity to a conventional bit. The actual state of the qubit after it has collapsed depends on the probabilities |a|2 and |b|2 immediately prior to the readout operation.
There are many different hardware and software approaches under consideration for use in quantum computers. One hardware approach uses integrated circuits formed of superconducting materials, such as aluminum or niobium. The technologies and processes involved in designing and fabricating superconducting integrated circuits are similar to those used for conventional integrated circuits.
Superconducting qubits are a type of superconducting device that can be included in a superconducting integrated circuit. Superconducting qubits can be separated into several categories depending on the physical property used to encode information. For example, they may be separated into charge, flux and phase devices, as discussed in, for example Makhlin et al., 2001, Reviews of Modern Physics 73, pp. 357-400. Charge devices store and manipulate information in the charge states of the device, where elementary charges consist of pairs of electrons called Cooper pairs. A Cooper pair has a charge of 2e and consists of two electrons bound together by, for example, a phonon interaction. See e.g., Nielsen and Chuang, Quantum Computation and Quantum Information, Cambridge University Press, Cambridge (2000), pp. 343-345. Flux devices store information in a variable related to the magnetic flux through some part of the device. Phase devices store information in a variable related to the difference is superconducting phase between two regions of the phase device. Recently, hybrid devices using two or more of charge, flux and phase degrees of freedom have been developed. See e.g., U.S. Pat. No. 6,838,694 and U.S. Patent Application No. 2005-0082519, where are hereby incorporated by reference in their entireties.
Classical Factoring Algorithms
There are many known classical algorithms that exist for computing the prime factorization of integers. These classical algorithms fall into two main categories: special-purpose algorithms and general purpose algorithms. The efficiency of special purpose algorithms is number dependent. That is, depending on the properties of the number, the time it takes for the special-purpose algorithm to find the factors greatly varies. If the algorithm gets “lucky” and gets a number that works well with it, the solution can be found fairly quickly. For some numbers, special purpose algorithms can fail to find a solution.
In contrast to special purpose algorithms, general purpose algorithms are almost guaranteed to work for any number. The run-time of general purpose algorithms depends solely on the size of the number being factored. For more information, see Lenstra, 2000, Designs, Codes, and Cryptography 19, 101-128.
Some examples of special purpose algorithms include Pollard's rho algorithm, William's p+1 algorithm, and Fermat's factorization method. Examples of general purpose algorithms include Dixon's algorithm, quadratic sieve, and general number field sieve. See Lenstra for more information about how factorization algorithms work. For very large numbers, general purpose algorithms are preferred. Currently, the largest RSA challenge biprime to be factored is a 200 digit number. The general number field sieve method was used to solve this number.
Known classical algorithms for prime factorization require substantial amounts of computational power. For example such problems typically require powerful computing architectures such as supercomputers, massively parallel computing systems, and distributed computing systems that operate over a network such as the Internet. Even with such powerful computing architectures, the run time of the algorithms is very long. For example, the 200 digit number took approximately 1.5 years to factor with a cluster of 80 computers operating at a clock speed of 2.2 GHz. For larger biprimes such as those used in encryption, which can be 300 digits or more, the calculation would require prohibitively large computational power and very long run times.
Quantum Factoring Algorithms
In 1994, Peter Shor developed an algorithm for factoring integers that is intended to be run on a quantum computer. Using the special properties of quantum computers, the algorithm is able to probabilistically factor in O((log N)3) time using O(log N) space, where space refers to the amount of computational memory needed and where N is the number to be factored. This polynomial run time was a significant improvement over the best classical algorithms, which ran in sub-exponential time. See Shor, 1997, SIAM J. Comput. 26, pp. 1484-1509. Recently, a group from IGM experimentally realized Shor's Algorithm by factoring the number fifteen using a rudimentary 7-qubit nuclear magnetic resonance (NMR) quantum computer. The group used circuit model quantum computing to implement their algorithm. See Vandersypen et al., 2001, Nature 414, 883. However, the Vandersypen et al. method utilized a priori knowledge of the answers. In addition, NMR computers, such as those used by Vandersypen et al. are not scalable, meaning that larger, more interesting numbers cannot be factored using the methods taught by Vandersypen et al.
A classical model of factoring, expressed as an optimization problem, is disclosed in Burges, 2002, Microsoft Technical Report MSR-TR-2002-83. That is, the method of Burges is different from other proposed algorithms because it attempts to map the prime factorization problem to an optimization problem rather than a decision problem. Optimization problems are a class of problems where the aim is the maximize or minimize one or more variables of the problem. In the case of Burges, the biprime and its factors are represented in bit form, with the factor bits being variables. Then, by using long multiplication of the factors to get the biprime, one can derive a set of factor equations. The factor equations are then reduced as much as possible and then cast into an optimization of coefficients in a single equation. The solution of the optimization problem should give the proper bit values of the factors, thus effectively factoring the biprime.
However, the drawback of the Burges algorithm is that it is limited to use on a classical computer. Optimization problems, though a different type of problem than prime factorization, can also take up a tremendous amount of computing power. Thus, the obstacle of sufficient resources still has not been solved.
Accordingly, there remains a need in the art for improved methods for prime factorization of large numbers.
In the figures, identical reference numbers identify similar elements or acts. The sizes and relative positions of elements in the figures are not necessarily drawn to scale. For example, the shapes of various elements and angles are not drawn to scale, and some of these elements are arbitrarily enlarged and positioned to improve legibility. Further, the particular shapes of the elements as drawn are not intended to convey any information regarding the actual shape of the particular elements and have been solely selected for ease of recognition in the figures. Furthermore, while the figures may show specific layouts, one skilled in the art will appreciate that variations in design, layout, and fabrication are possible and the shown layouts are not to be construed as limiting the layout of the present systems, methods and apparatus.